package com.example.exercises;

import com.example.structure.ListNode;

/**
 * @author wxz
 * <p>
 * 82. 删除排序链表中的重复元素 II
 * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
 * <p>
 * 返回同样按升序排列的结果链表。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：head = [1,2,3,3,4,4,5]
 * 输出：[1,2,5]
 * <p>
 * 思路：dummy为head前的一个节点。用于最后返回使用。
 * 因为这个是删除重复的所有元素，而不是去重。所以我们要从dummy节点开始遍历，防止开始的就是重复的。
 * <p>
 * 解题的核心点是用一个指针去维护整个链表。比较cur.next和 cur.next.next，如果相等就记录这个值（可以让所有遍历节点都和这个重复值比较），然后后移指针
 * 这样就可以删除掉所有的重复元素。
 */
public class RemoveDuplicatesfromSortedListII {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;
    }

}
